package algorithm.niuke;

public class 复杂链表的复制 {
    
    public class RandomListNode {
        int label;
        RandomListNode next = null;
        RandomListNode random = null;

        RandomListNode(int label) {
            this.label = label;
        }
    }
    
    public class Solution {
        public RandomListNode Clone(RandomListNode pHead)
        {
            
            RandomListNode head = null;
            if (pHead != null) {
                head = new RandomListNode(pHead.label);
            }else{
                return null;
            }
            RandomListNode pPre = pHead;
            RandomListNode pNext = pPre.next;
            RandomListNode pre = head;

            head.random = pPre;
            pPre.next = head;

            while (pNext != null) {
                RandomListNode newNode = new RandomListNode(pNext.label);
                pre.next = newNode;
                pPre = pNext;
                pNext = pNext.next;

                newNode.random = pPre;
                pPre.next = newNode;
            }
            pre = head;
            while (pre != null) {
                RandomListNode next = pre.next;
                RandomListNode random = pre.random;
                if (random != null) {
                    if(random.random != null){
                        pre.random = random.random.next;
                    }else{
                        pre.random = null;
                    }   
                }
                pre = next;
            }
            return head;
        }
    }
    
    public RandomListNode Clone2(RandomListNode pHead)
    {
        
        RandomListNode head = null;
        if (pHead != null) {
            head = new RandomListNode(pHead.label);
        }else{
            return null;
        }
        pHead.label = 0;
        RandomListNode pNext = pHead.next;
        RandomListNode pre = head;
        RandomListNode[] randomOrder = new RandomListNode[100000];
        int size = 0;
        randomOrder[size++]=head;
        
        while (pNext != null) {
            RandomListNode nextNode = new RandomListNode(pNext.label);
            randomOrder[size++] = nextNode;
            pre.next = nextNode;
            pre = nextNode;
            pNext.label = size-1;
            pNext = pNext.next;
        }
        
        RandomListNode pP = pHead;
        RandomListNode p = head;
        while(pP!=null){
            RandomListNode random = pP.random;
            if(random!=null){
                int index = random.label;
                p.random = randomOrder[index];
            }
            pP = pP.next;
            p = p.next;
        }
        return head;
    }
}
